package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class NQueens {
	List<List<String>> ret;
    List<String> path;
    public boolean[][] check; //标记所有位置是否被使用过
    
    //构造每一层的字符串
    public String getString(int n,int pos){
        char[] s=new char[n];
        Arrays.fill(s, '.');
        s[pos]='Q';
        return new String(s);
    }

    //判断[i,j]位置是否能放置皇后
    public boolean judge(int n,int i,int j){
    
    	//判断列
        for(int k=0;k<n;k++){
            if(check[i][k]==true&&j!=k){
                return false;
            }
        }
        
        //判断主对角线
        int p=i;
        int q=j;
        while(p>0&&q>0){
            p--;
            q--;
        }
        for(;p<n&&q<n;p++,q++){
            if(check[p][q]==true&&p!=i&&q!=j){
                return false;
            }
        }

        //判断副对角线
        p=i;
        q=j;
        while(p>0&&q<n-1){
            p--;
            q++;
        }
        for(;p<n&&q>=0;p++,q--){
            if(check[p][q]==true&&p!=i&&q!=j){
                return false;
            }
        }
        return true;
    }
    
    //pos: 当前在处理第几层
    public void dfs(int n,int pos){
        if(path.size()==n){
            ret.add(new ArrayList(path));
            return ;
        }

        for(int i=0;i<n;i++){
            if(pos==0||judge(n,pos,i)==true){
                path.add(new String(getString(n,i)));
                check[pos][i]=true;
                dfs(n,pos+1);
                path.remove(path.size()-1);
                check[pos][i]=false;
            }
        }
    }
    public List<List<String>> solveNQueens(int n) {
        ret=new ArrayList<>();
        path=new ArrayList();
        check=new boolean[n][n];
        dfs(n,0);
        return ret;
    }
}
